package microsoft;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

public class Test3 {
    public static void main(String[] args) {
        int[] A = {1,2,1,6,8,7,8}, B = {2,3,4,7,7,8,7};
        new Test3().solution(A, B, 10);
    }

    /**
     * 判断是否能安排成功时需要进行递归判断，并去除重复
     * @param A 患者喜欢的医生
     * @param B 患者喜欢的医生
     * @param S 医生数量
     * @return 是否能全部安排
     */
    public boolean solution(int[] A, int[] B, int S) {
        if (S < A.length) return false;
        Map<Integer, Integer> map = new HashMap<>();
        int len = A.length;
        for (int i = 0; i < len; i++) {
            if (!build(i, map,A, B, new HashSet<>())) {
                return false;
            }
        }
        return true;
    }
    public boolean build(int patient, Map<Integer, Integer> map, int[] A, int[] B, Set<Integer> visited){
        int doctorA = A[patient], doctorB = B[patient];
        if (!map.containsKey(doctorA)){
            map.put(doctorA, patient);
            return true;
        }
        if (!map.containsKey(doctorB)){
            map.put(doctorB, patient);
            return true;
        }
        // 这里需要重排了
        visited.add(patient);
        int p = map.get(doctorA);
        if (!visited.contains(p)){
            visited.add(p);
            map.put(doctorA, patient);
            if (build(p, map, A, B, visited)){
                return true;
            }
            visited.remove(p);
            map.put(doctorA, p);
        }
        p = map.get(doctorB);
        if (!visited.contains(p)){
            visited.add(p);
            map.put(doctorB, patient);
            if (build(p, map, A, B, visited)){
                return true;
            }
            visited.remove(p);
            map.put(doctorB, p);
        }
        return false;
    }
}
